/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  if (n == 1)
    return ['()'];
  let res = [],
    stack = [],
    // 用于标记当前使用过的左括号、有括号的数量
    left = 0,
    right = 0;

  function dfs(depth) {
    if (depth == n * 2) {
      res.push(stack.join(''));
      return;
    }
    if (left == n) {
      // 1.left为n的时候，表示左括号已经满了，此时只能添加右括号
      stack.push(')');
      right++;
      dfs(depth + 1);
      stack.splice(stack.length - 1, 1);
      right--;
    } else if (left == 0) {
      // 2.left为0的时候，表示左括号为0,此时必须先添加左括号
      stack.push('(');
      left++;
      dfs(depth + 1);
      stack.splice(stack.length - 1, 1);
      left--;
    } else {
      // 3.除了以上情况，可以选择性添加左括号和有括号
      // 3.1 左括号一定能添加
      stack.push('(');
      left++;
      dfs(depth + 1);
      stack.splice(stack.length - 1, 1);
      left--;
      // 3.2 当右括号的数量小于左括号的时候，才能添加右括号
      if(right < left) {
        stack.push(')');
        right++;
        dfs(depth + 1);
        stack.splice(stack.length - 1, 1);
        right--;
      }
    }
  }

  dfs(0);
  return res;

};
let n = 3;
console.log(generateParenthesis(n));
n = 1;
console.log(generateParenthesis(n));
